package org.tonny.algorithm.leetcode;

import java.util.*;

/**
 * 57. 插入区间
 */
public class LeetCode57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 数据整合到一起
        List<int[]> mergeResult = new LinkedList<>(Arrays.asList(intervals));
        mergeResult.add(newInterval);
        //排序，先以左边为准，相同则以右边为准
        mergeResult.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] left, int[] right) {
                if (left[0] != right[0]) {
                    return left[0] - right[0];
                } else {
                    return left[1] - right[1];
                }
            }
        });
        LinkedList<int[]> result = new LinkedList<>();
        result.add(mergeResult.get(0));
        for (int i = 1; i < mergeResult.size(); i++) {
            int[] last = result.getLast();
            int[] curr = mergeResult.get(i);

            //已知[a,b] [c,d] a<=c;    如果b>=d,丢弃当前区间
            if (last[1] >= curr[1]) {//上一个区间覆盖了当前区间，丢弃当前区间
                continue;
            }
            //已知[a,b] [c,d] a<=c;b<d;    如果b>=c,则新区间为[a,d]
            if (last[1] >= curr[0]) {//上一个区间覆盖了当前区间，丢弃当前区间
                last[1] = curr[1];
                continue;
            }
            //已知[a,b] [c,d] a<=c;bd;    如果b<c,则两个区间无重叠,直接添加
            result.add(curr);
        }


        int[][] r = new int[result.size()][2];
        for (int i = 0; i < result.size(); i++) {
            r[i][0] = result.get(i)[0];
            r[i][1] = result.get(i)[1];
        }
        return r;
    }
}